home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cocktail / reuse.lha / reuse / m2c / Sets.c < prev    next >
C/C++ Source or Header  |  1992-08-18  |  12KB  |  734 lines
  1. #include "SYSTEM_.h"
  2.  
  3. #ifndef DEFINITION_General
  4. #include "General.h"
  5. #endif
  6.  
  7. #ifndef DEFINITION_DynArray
  8. #include "DynArray.h"
  9. #endif
  10.  
  11. #ifndef DEFINITION_IO
  12. #include "IO.h"
  13. #endif
  14.  
  15. #ifndef DEFINITION_Sets
  16. #include "Sets.h"
  17. #endif
  18.  
  19.  
  20. #define BitsPerBitset    32
  21. #define BitsPerByte    8
  22. #define BytesPerBitset    (BitsPerBitset / BitsPerByte)
  23. #define NoCard    -1
  24. static BITSET AllBits;
  25. static IO_tFile g;
  26. static void WriteElmt ARGS((CARDINAL Elmt));
  27.  
  28.  
  29. void Sets_MakeSet
  30. # ifdef __STDC__
  31. (Sets_tSet *Set, CARDINAL MaxSize)
  32. # else
  33. (Set, MaxSize)
  34. Sets_tSet *Set;
  35. CARDINAL MaxSize;
  36. # endif
  37. {
  38.   LONGINT ElmtCount;
  39.  
  40.   {
  41.     register Sets_tSet *W_1 = Set;
  42.  
  43.     ElmtCount = (MaxSize + BitsPerBitset - MaxSize % BitsPerBitset) / BitsPerBitset;
  44.     DynArray_MakeArray((ADDRESS *)&W_1->BitsetPtr, &ElmtCount, (LONGINT)BytesPerBitset);
  45.     W_1->MaxElmt = MaxSize;
  46.     W_1->LastBitset = ElmtCount - 1;
  47.     Sets_AssignEmpty(Set);
  48.   }
  49. }
  50.  
  51. void Sets_ReleaseSet
  52. # ifdef __STDC__
  53. (Sets_tSet *Set)
  54. # else
  55. (Set)
  56. Sets_tSet *Set;
  57. # endif
  58. {
  59.   LONGINT ElmtCount;
  60.  
  61.   ElmtCount = Set->LastBitset + 1;
  62.   DynArray_ReleaseArray((ADDRESS *)&Set->BitsetPtr, &ElmtCount, (LONGINT)BytesPerBitset);
  63. }
  64.  
  65. void Sets_Union
  66. # ifdef __STDC__
  67. (Sets_tSet *Set1, Sets_tSet Set2)
  68. # else
  69. (Set1, Set2)
  70. Sets_tSet *Set1;
  71. Sets_tSet Set2;
  72. # endif
  73. {
  74.   CARDINAL i;
  75.  
  76.   {
  77.     register Sets_tSet *W_2 = Set1;
  78.  
  79.     i = 0;
  80.     while (i <= W_2->LastBitset) {
  81.       W_2->BitsetPtr->A[i] = W_2->BitsetPtr->A[i] | Set2.BitsetPtr->A[i];
  82.       INC(i);
  83.     }
  84.     W_2->Card = NoCard;
  85.     W_2->FirstElmt = General_Min((LONGINT)W_2->FirstElmt, (LONGINT)Set2.FirstElmt);
  86.     W_2->LastElmt = General_Max((LONGINT)W_2->LastElmt, (LONGINT)Set2.LastElmt);
  87.   }
  88. }
  89.  
  90. void Sets_Difference
  91. # ifdef __STDC__
  92. (Sets_tSet *Set1, Sets_tSet Set2)
  93. # else
  94. (Set1, Set2)
  95. Sets_tSet *Set1;
  96. Sets_tSet Set2;
  97. # endif
  98. {
  99.   CARDINAL i;
  100.  
  101.   {
  102.     register Sets_tSet *W_3 = Set1;
  103.  
  104.     i = 0;
  105.     while (i <= W_3->LastBitset) {
  106.       W_3->BitsetPtr->A[i] = SET_DIFF(W_3->BitsetPtr->A[i], Set2.BitsetPtr->A[i]);
  107.       INC(i);
  108.     }
  109.     W_3->Card = NoCard;
  110.   }
  111. }
  112.  
  113. void Sets_Intersection
  114. # ifdef __STDC__
  115. (Sets_tSet *Set1, Sets_tSet Set2)
  116. # else
  117. (Set1, Set2)
  118. Sets_tSet *Set1;
  119. Sets_tSet Set2;
  120. # endif
  121. {
  122.   CARDINAL i;
  123.  
  124.   {
  125.     register Sets_tSet *W_4 = Set1;
  126.  
  127.     i = 0;
  128.     while (i <= W_4->LastBitset) {
  129.       W_4->BitsetPtr->A[i] = W_4->BitsetPtr->A[i] & Set2.BitsetPtr->A[i];
  130.       INC(i);
  131.     }
  132.     W_4->Card = NoCard;
  133.     W_4->FirstElmt = General_Max((LONGINT)W_4->FirstElmt, (LONGINT)Set2.FirstElmt);
  134.     W_4->LastElmt = General_Min((LONGINT)W_4->LastElmt, (LONGINT)Set2.LastElmt);
  135.   }
  136. }
  137.  
  138. void Sets_SymDiff
  139. # ifdef __STDC__
  140. (Sets_tSet *Set1, Sets_tSet Set2)
  141. # else
  142. (Set1, Set2)
  143. Sets_tSet *Set1;
  144. Sets_tSet Set2;
  145. # endif
  146. {
  147.   CARDINAL i;
  148.  
  149.   {
  150.     register Sets_tSet *W_5 = Set1;
  151.  
  152.     i = 0;
  153.     while (i <= W_5->LastBitset) {
  154.       W_5->BitsetPtr->A[i] = W_5->BitsetPtr->A[i] ^ Set2.BitsetPtr->A[i];
  155.       INC(i);
  156.     }
  157.     W_5->Card = NoCard;
  158.     W_5->FirstElmt = General_Min((LONGINT)W_5->FirstElmt, (LONGINT)Set2.FirstElmt);
  159.     W_5->LastElmt = General_Max((LONGINT)W_5->LastElmt, (LONGINT)Set2.LastElmt);
  160.   }
  161. }
  162.  
  163. void Sets_Complement
  164. # ifdef __STDC__
  165. (Sets_tSet *Set)
  166. # else
  167. (Set)
  168. Sets_tSet *Set;
  169. # endif
  170. {
  171.   SHORTINT i;
  172.   BITSET s;
  173.  
  174.   {
  175.     register Sets_tSet *W_6 = Set;
  176.  
  177.     i = 0;
  178.     while (i <= (SHORTINT)W_6->LastBitset - 1) {
  179.       W_6->BitsetPtr->A[i] = SET_DIFF(AllBits, W_6->BitsetPtr->A[i]);
  180.       INC(i);
  181.     }
  182.     s = 0X0L;
  183.     {
  184.       SHORTINT B_1 = 0, B_2 = (SHORTINT)W_6->MaxElmt % BitsPerBitset;
  185.  
  186.       if (B_1 <= B_2)
  187.         for (i = B_1;; i += 1) {
  188.           INCL(s, (SHORTCARD)i);
  189.           if (i >= B_2) break;
  190.         }
  191.     }
  192.     W_6->BitsetPtr->A[W_6->LastBitset] = SET_DIFF(s, W_6->BitsetPtr->A[W_6->LastBitset]);
  193.     if (W_6->Card != NoCard) {
  194.       W_6->Card = (SHORTINT)W_6->MaxElmt + 1 - W_6->Card;
  195.     }
  196.     W_6->FirstElmt = 0;
  197.     W_6->LastElmt = W_6->MaxElmt;
  198.   }
  199. }
  200.  
  201. void Sets_Include
  202. # ifdef __STDC__
  203. (Sets_tSet *Set, CARDINAL Elmt)
  204. # else
  205. (Set, Elmt)
  206. Sets_tSet *Set;
  207. CARDINAL Elmt;
  208. # endif
  209. {
  210.   {
  211.     register Sets_tSet *W_7 = Set;
  212.  
  213.     INCL(W_7->BitsetPtr->A[Elmt / BitsPerBitset], Elmt % BitsPerBitset);
  214.     W_7->Card = NoCard;
  215.     if (W_7->FirstElmt > Elmt) {
  216.       W_7->FirstElmt = Elmt;
  217.     }
  218.     if (W_7->LastElmt < Elmt) {
  219.       W_7->LastElmt = Elmt;
  220.     }
  221.   }
  222. }
  223.  
  224. void Sets_Exclude
  225. # ifdef __STDC__
  226. (Sets_tSet *Set, CARDINAL Elmt)
  227. # else
  228. (Set, Elmt)
  229. Sets_tSet *Set;
  230. CARDINAL Elmt;
  231. # endif
  232. {
  233.   {
  234.     register Sets_tSet *W_8 = Set;
  235.  
  236.     EXCL(W_8->BitsetPtr->A[Elmt / BitsPerBitset], Elmt % BitsPerBitset);
  237.     W_8->Card = NoCard;
  238.     if (Elmt == W_8->FirstElmt && Elmt < W_8->MaxElmt) {
  239.       INC(W_8->FirstElmt);
  240.     }
  241.     if (Elmt == W_8->LastElmt && Elmt > 0) {
  242.       DEC(W_8->LastElmt);
  243.     }
  244.   }
  245. }
  246.  
  247. CARDINAL Sets_Card
  248. # ifdef __STDC__
  249. (Sets_tSet *Set)
  250. # else
  251. (Set)
  252. Sets_tSet *Set;
  253. # endif
  254. {
  255.   CARDINAL i;
  256.  
  257.   {
  258.     register Sets_tSet *W_9 = Set;
  259.  
  260.     if (W_9->Card == NoCard) {
  261.       W_9->Card = 0;
  262.       {
  263.         LONGCARD B_3 = W_9->FirstElmt, B_4 = W_9->LastElmt;
  264.  
  265.         if (B_3 <= B_4)
  266.           for (i = B_3;; i += 1) {
  267.             if (Sets_IsElement(i, Set)) {
  268.               INC(W_9->Card);
  269.             }
  270.             if (i >= B_4) break;
  271.           }
  272.       }
  273.     }
  274.     return W_9->Card;
  275.   }
  276. }
  277.  
  278. CARDINAL Sets_Size
  279. # ifdef __STDC__
  280. (Sets_tSet *Set)
  281. # else
  282. (Set)
  283. Sets_tSet *Set;
  284. # endif
  285. {
  286.   return Set->MaxElmt;
  287. }
  288.  
  289. CARDINAL Sets_Minimum
  290. # ifdef __STDC__
  291. (Sets_tSet *Set)
  292. # else
  293. (Set)
  294. Sets_tSet *Set;
  295. # endif
  296. {
  297.   CARDINAL i;
  298.  
  299.   {
  300.     register Sets_tSet *W_10 = Set;
  301.  
  302.     i = W_10->FirstElmt;
  303.     while (i <= W_10->LastElmt) {
  304.       if (Sets_IsElement(i, Set)) {
  305.         W_10->FirstElmt = i;
  306.         return i;
  307.       }
  308.       INC(i);
  309.     }
  310.     return 0;
  311.   }
  312. }
  313.  
  314. CARDINAL Sets_Maximum
  315. # ifdef __STDC__
  316. (Sets_tSet *Set)
  317. # else
  318. (Set)
  319. Sets_tSet *Set;
  320. # endif
  321. {
  322.   CARDINAL i;
  323.  
  324.   {
  325.     register Sets_tSet *W_11 = Set;
  326.  
  327.     i = W_11->LastElmt;
  328.     while (i >= W_11->FirstElmt) {
  329.       if (Sets_IsElement(i, Set)) {
  330.         W_11->LastElmt = i;
  331.         return i;
  332.       }
  333.       DEC(i);
  334.     }
  335.     return 0;
  336.   }
  337. }
  338.  
  339. CARDINAL Sets_Select
  340. # ifdef __STDC__
  341. (Sets_tSet *Set)
  342. # else
  343. (Set)
  344. Sets_tSet *Set;
  345. # endif
  346. {
  347.   return Sets_Minimum(Set);
  348. }
  349.  
  350. CARDINAL Sets_Extract
  351. # ifdef __STDC__
  352. (Sets_tSet *Set)
  353. # else
  354. (Set)
  355. Sets_tSet *Set;
  356. # endif
  357. {
  358.   CARDINAL i;
  359.  
  360.   i = Sets_Minimum(Set);
  361.   Sets_Exclude(Set, i);
  362.   return i;
  363. }
  364.  
  365. BOOLEAN Sets_IsSubset
  366. # ifdef __STDC__
  367. (Sets_tSet Set1, Sets_tSet Set2)
  368. # else
  369. (Set1, Set2)
  370. Sets_tSet Set1, Set2;
  371. # endif
  372. {
  373.   CARDINAL i;
  374.  
  375.   {
  376.     register Sets_tSet *W_12 = &Set1;
  377.  
  378.     i = 0;
  379.     while (i <= W_12->LastBitset) {
  380.       if (!SET_IS_SUBSET1(W_12->BitsetPtr->A[i], Set2.BitsetPtr->A[i])) {
  381.         return FALSE;
  382.       }
  383.       INC(i);
  384.     }
  385.     return TRUE;
  386.   }
  387. }
  388.  
  389. BOOLEAN Sets_IsStrictSubset
  390. # ifdef __STDC__
  391. (Sets_tSet Set1, Sets_tSet Set2)
  392. # else
  393. (Set1, Set2)
  394. Sets_tSet Set1, Set2;
  395. # endif
  396. {
  397.   return Sets_IsSubset(Set1, Set2) && Sets_IsNotEqual(Set1, Set2);
  398. }
  399.  
  400. BOOLEAN Sets_IsEqual
  401. # ifdef __STDC__
  402. (Sets_tSet *Set1, Sets_tSet *Set2)
  403. # else
  404. (Set1, Set2)
  405. Sets_tSet *Set1, *Set2;
  406. # endif
  407. {
  408.   CARDINAL i;
  409.  
  410.   {
  411.     register Sets_tSet *W_13 = Set1;
  412.  
  413.     i = 0;
  414.     while (i <= W_13->LastBitset) {
  415.       if (W_13->BitsetPtr->A[i] != Set2->BitsetPtr->A[i]) {
  416.         return FALSE;
  417.       }
  418.       INC(i);
  419.     }
  420.     return TRUE;
  421.   }
  422. }
  423.  
  424. BOOLEAN Sets_IsNotEqual
  425. # ifdef __STDC__
  426. (Sets_tSet Set1, Sets_tSet Set2)
  427. # else
  428. (Set1, Set2)
  429. Sets_tSet Set1, Set2;
  430. # endif
  431. {
  432.   return !Sets_IsEqual(&Set1, &Set2);
  433. }
  434.  
  435. BOOLEAN Sets_IsElement
  436. # ifdef __STDC__
  437. (CARDINAL Elmt, Sets_tSet *Set)
  438. # else
  439. (Elmt, Set)
  440. CARDINAL Elmt;
  441. Sets_tSet *Set;
  442. # endif
  443. {
  444.   return IN(Elmt % BitsPerBitset, Set->BitsetPtr->A[Elmt / BitsPerBitset]);
  445. }
  446.  
  447. BOOLEAN Sets_IsEmpty
  448. # ifdef __STDC__
  449. (Sets_tSet Set)
  450. # else
  451. (Set)
  452. Sets_tSet Set;
  453. # endif
  454. {
  455.   CARDINAL i;
  456.  
  457.   {
  458.     register Sets_tSet *W_14 = &Set;
  459.  
  460.     if (W_14->FirstElmt <= W_14->LastElmt) {
  461.       i = 0;
  462.       while (i <= W_14->LastBitset) {
  463.         if (W_14->BitsetPtr->A[i] != 0X0L) {
  464.           return FALSE;
  465.         }
  466.         INC(i);
  467.       }
  468.     }
  469.     return TRUE;
  470.   }
  471. }
  472.  
  473. BOOLEAN Sets_Forall
  474. # ifdef __STDC__
  475. (Sets_tSet Set, Sets_ProcOfCardToBool Proc)
  476. # else
  477. (Set, Proc)
  478. Sets_tSet Set;
  479. Sets_ProcOfCardToBool Proc;
  480. # endif
  481. {
  482.   CARDINAL i;
  483.  
  484.   {
  485.     register Sets_tSet *W_15 = &Set;
  486.  
  487.     {
  488.       LONGCARD B_5 = W_15->FirstElmt, B_6 = W_15->LastElmt;
  489.  
  490.       if (B_5 <= B_6)
  491.         for (i = B_5;; i += 1) {
  492.           if (Sets_IsElement(i, &Set) && !(*Proc)(i)) {
  493.             return FALSE;
  494.           }
  495.           if (i >= B_6) break;
  496.         }
  497.     }
  498.     return TRUE;
  499.   }
  500. }
  501.  
  502. BOOLEAN Sets_Exists
  503. # ifdef __STDC__
  504. (Sets_tSet Set, Sets_ProcOfCardToBool Proc)
  505. # else
  506. (Set, Proc)
  507. Sets_tSet Set;
  508. Sets_ProcOfCardToBool Proc;
  509. # endif
  510. {
  511.   CARDINAL i;
  512.  
  513.   {
  514.     register Sets_tSet *W_16 = &Set;
  515.  
  516.     {
  517.       LONGCARD B_7 = W_16->FirstElmt, B_8 = W_16->LastElmt;
  518.  
  519.       if (B_7 <= B_8)
  520.         for (i = B_7;; i += 1) {
  521.           if (Sets_IsElement(i, &Set) && (*Proc)(i)) {
  522.             return TRUE;
  523.           }
  524.           if (i >= B_8) break;
  525.         }
  526.     }
  527.     return FALSE;
  528.   }
  529. }
  530.  
  531. BOOLEAN Sets_Exists1
  532. # ifdef __STDC__
  533. (Sets_tSet Set, Sets_ProcOfCardToBool Proc)
  534. # else
  535. (Set, Proc)
  536. Sets_tSet Set;
  537. Sets_ProcOfCardToBool Proc;
  538. # endif
  539. {
  540.   CARDINAL i, n;
  541.  
  542.   {
  543.     register Sets_tSet *W_17 = &Set;
  544.  
  545.     n = 0;
  546.     {
  547.       LONGCARD B_9 = W_17->FirstElmt, B_10 = W_17->LastElmt;
  548.  
  549.       if (B_9 <= B_10)
  550.         for (i = B_9;; i += 1) {
  551.           if (Sets_IsElement(i, &Set) && (*Proc)(i)) {
  552.             INC(n);
  553.           }
  554.           if (i >= B_10) break;
  555.         }
  556.     }
  557.     return n == 1;
  558.   }
  559. }
  560.  
  561. void Sets_Assign
  562. # ifdef __STDC__
  563. (Sets_tSet *Set1, Sets_tSet Set2)
  564. # else
  565. (Set1, Set2)
  566. Sets_tSet *Set1;
  567. Sets_tSet Set2;
  568. # endif
  569. {
  570.   CARDINAL i;
  571.  
  572.   {
  573.     register Sets_tSet *W_18 = Set1;
  574.  
  575.     i = 0;
  576.     while (i <= W_18->LastBitset) {
  577.       W_18->BitsetPtr->A[i] = Set2.BitsetPtr->A[i];
  578.       INC(i);
  579.     }
  580.     W_18->Card = Set2.Card;
  581.     W_18->FirstElmt = Set2.FirstElmt;
  582.     W_18->LastElmt = Set2.LastElmt;
  583.   }
  584. }
  585.  
  586. void Sets_AssignElmt
  587. # ifdef __STDC__
  588. (Sets_tSet *Set, CARDINAL Elmt)
  589. # else
  590. (Set, Elmt)
  591. Sets_tSet *Set;
  592. CARDINAL Elmt;
  593. # endif
  594. {
  595.   {
  596.     register Sets_tSet *W_19 = Set;
  597.  
  598.     Sets_AssignEmpty(Set);
  599.     Sets_Include(Set, Elmt);
  600.     W_19->Card = 1;
  601.     W_19->FirstElmt = Elmt;
  602.     W_19->LastElmt = Elmt;
  603.   }
  604. }
  605.  
  606. void Sets_AssignEmpty
  607. # ifdef __STDC__
  608. (Sets_tSet *Set)
  609. # else
  610. (Set)
  611. Sets_tSet *Set;
  612. # endif
  613. {
  614.   CARDINAL i;
  615.  
  616.   {
  617.     register Sets_tSet *W_20 = Set;
  618.  
  619.     i = 0;
  620.     while (i <= W_20->LastBitset) {
  621.       W_20->BitsetPtr->A[i] = 0X0L;
  622.       INC(i);
  623.     }
  624.     W_20->Card = 0;
  625.     W_20->FirstElmt = W_20->MaxElmt;
  626.     W_20->LastElmt = 0;
  627.   }
  628. }
  629.  
  630. void Sets_ForallDo
  631. # ifdef __STDC__
  632. (Sets_tSet Set, Sets_ProcOfCard Proc)
  633. # else
  634. (Set, Proc)
  635. Sets_tSet Set;
  636. Sets_ProcOfCard Proc;
  637. # endif
  638. {
  639.   CARDINAL i;
  640.  
  641.   {
  642.     register Sets_tSet *W_21 = &Set;
  643.  
  644.     {
  645.       LONGCARD B_11 = W_21->FirstElmt, B_12 = W_21->LastElmt;
  646.  
  647.       if (B_11 <= B_12)
  648.         for (i = B_11;; i += 1) {
  649.           if (Sets_IsElement(i, &Set)) {
  650.             (*Proc)(i);
  651.           }
  652.           if (i >= B_12) break;
  653.         }
  654.     }
  655.   }
  656. }
  657.  
  658. void Sets_ReadSet
  659. # ifdef __STDC__
  660. (IO_tFile f, Sets_tSet *Set)
  661. # else
  662. (f, Set)
  663. IO_tFile f;
  664. Sets_tSet *Set;
  665. # endif
  666. {
  667.   CARDINAL card;
  668.  
  669.   do {
  670.   } while (!(IO_ReadC(f) == '{'));
  671.   Sets_AssignEmpty(Set);
  672.   card = 0;
  673.   for (;;) {
  674.     if (IO_ReadC(f) == '}') {
  675.       goto EXIT_1;
  676.     }
  677.     Sets_Include(Set, (LONGCARD)IO_ReadI(f));
  678.     INC(card);
  679.   } EXIT_1:;
  680.   Set->Card = card;
  681. }
  682.  
  683. void Sets_WriteSet
  684. # ifdef __STDC__
  685. (IO_tFile f, Sets_tSet Set)
  686. # else
  687. (f, Set)
  688. IO_tFile f;
  689. Sets_tSet Set;
  690. # endif
  691. {
  692.   {
  693.     register Sets_tSet *W_22 = &Set;
  694.  
  695.     g = f;
  696.     IO_WriteC(f, '{');
  697.     Sets_ForallDo(Set, (Sets_ProcOfCard)WriteElmt);
  698.     IO_WriteC(f, '}');
  699.   }
  700. }
  701.  
  702. static void WriteElmt
  703. # ifdef __STDC__
  704. (CARDINAL Elmt)
  705. # else
  706. (Elmt)
  707. CARDINAL Elmt;
  708. # endif
  709. {
  710.   IO_WriteC(g, ' ');
  711.   IO_WriteI(g, (LONGINT)Elmt, 0L);
  712. }
  713.  
  714. void BEGIN_Sets()
  715. {
  716.   static BOOLEAN has_been_called = FALSE;
  717.  
  718.   if (!has_been_called) {
  719.     has_been_called = TRUE;
  720.  
  721.     BEGIN_IO();
  722.     BEGIN_General();
  723.     BEGIN_DynArray();
  724.     BEGIN_IO();
  725.  
  726.     AllBits = SET_cRNG(0, BitsPerBitset - 1);
  727.     if (sizeof(BITSET) != BytesPerBitset) {
  728.       IO_WriteS((System_tFile)IO_StdError, (STRING)"TSIZE (BITSET) = ", 17L);
  729.       IO_WriteI((System_tFile)IO_StdError, (LONGINT)sizeof(BITSET), 0L);
  730.       IO_WriteNl((System_tFile)IO_StdError);
  731.     }
  732.   }
  733. }
  734.